package Solution.problem060;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/05/31 09:57
 */
public class Solution {
    public static String getPermutation(int n, int k) {
        if(n<1){
            return null;
        }
        int[] nums=new int[n];
        int value=1;
        for(int i=0;i<n;i++){
            nums[i]=value;
            value++;
        }
        while (k>1){
            nextPermutation(nums);
            k--;
        }
        StringBuilder builder=new StringBuilder();
        for(int i=0;i<n;i++){
            builder.append(nums[i]);
        }
        return builder.toString();
    }

    private static boolean nextPermutation(int[] nums){
        if(nums.length==1){
            return false;
        }

        /** 563210 从末尾开始找到一个可以交换的为止，因为是排序好的，只需要前面一位小于后面一位就可以了*/
        int p=-1;
        for(int i=nums.length-2;i>=0;i--){
            /** 找到n=0才找到*/
            if(nums[i]<nums[i+1]){
                p=i;
                break;
            }
        }
        /** 如果p是-1的话，证明已经是最大了，找不到下一个了，降序排列了*/
        if(p==-1){
            return false;
        }

        /** 从末尾找到第一个大于nums[p]的*/
        int tmp=nums[p];
        int q = nums.length - 1;
        while (nums[q] <= tmp) {
            q--;
        }
        /** 交换p和q的位置*/
        nums[p]=nums[q];
        nums[q]=tmp;

        /* 反转交换位置后面的数据*/
        reverse(p+1,nums);
        return true;
    }
    public static void reverse(int k, int[] nums) {
        if (k >= nums.length) return;
        int i = k;
        int j = nums.length - 1;
        while (i < j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            i++;
            j--;
        }
    }

    public static void main(String[] args){
        String result1=getPermutation(3,3);
        System.out.println(result1);
       String result2=getPermutation(4,9);
        System.out.println(result2);
        String result3=getPermutation(0,0);
        System.out.println(result3);


    }
}
